package acm.集美大学;

import java.util.*;

public class L缝合怪的作品 {
    static String[] strs;
    static Map<String, Set<Integer>> map=new HashMap<>();
    static int n,m;

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        strs=new String[n+1];
        for (int i = 1; i <= n; i++) {
            strs[i]=sc.next();
            Set<Integer> list = map.get(strs[i]);
            if (list==null){
                list=new HashSet<>();
                map.put(strs[i], list);
            }
            list.add(i);
        }
        for (int i = 0; i < m; i++) {
            int op = sc.nextInt();
            if (op==1){
                String a = sc.next();
                String b = sc.next();
                op1(a,b);
            }else {
                int i1 = sc.nextInt();
                String b = sc.next();
                op2(i1,b);
            }
        }
        for (int i = 1; i < strs.length; i++) {
            System.out.print(strs[i]+" ");
        }
        System.out.println();
    }
    public static void op1(String a,String b){
        Set<Integer> setA = map.get(a);
        if (setA==null) return;
        for (Integer i : setA) {
            strs[i]=b;
        }
        map.remove(a);
        Set<Integer> setB = map.get(b);
        if (setB==null){
            setB=new HashSet<>();
            map.put(b,setB);
        }
        setB.addAll(setA);
    }
    public static void op2(int a,String b){
        Set<Integer> setA = map.get(strs[a]);
        setA.remove(a);
        if (setA.isEmpty()){
            map.remove(strs[a]);
        }
        strs[a]=b;
        Set<Integer> setB = map.get(b);
        if (setB==null){
            setB=new HashSet<>();
            map.put(b,setB);
        }
        setB.add(a);
    }
}
